package net.lainiao.leetcode.LeetCode;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by Administrator on 2018/1/24.
 */
public class LeetCode198 {
    //小偷偷钱包的问题
    public static void main(String[] args) {
        int[] nums={1,2,3,4,5,6,7,8,11,10,9,12,13,14,15};
        LeetCode198 code198=new LeetCode198();
        int maxMoney=code198.rob(nums);
        System.out.println(maxMoney);
    }

    public int rob(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        Map<Integer,Integer> map=new HashMap<>();
        return robots(0,nums,map);
    }

    private int robots(int ind, int[] nums,Map<Integer,Integer> map) {
        if(ind>=nums.length){
            return 0;
        }
        if(map.containsKey(ind)){
            return map.get(ind);
        }
        int a=nums[ind]+robots(ind+2,nums,map);
        int b=robots(ind+1,nums,map);
        int result=Math.max(a,b);
        map.put(ind,result);
        return result;
    }


}
